package graph;

import java.util.*;
public class CloneGraph133 {
    public Node cloneGraph(Node node) {
        if(node==null){
            return node;
        }
        HashMap<Node,Node> map = new HashMap<>();
        Set<Node> visited = new HashSet<>();
        LinkedList<Node> deque = new LinkedList<>();
        deque.offer(node);
        while (deque.size()!=0){
            Node n = deque.poll();
            if(visited.contains(n)){
                continue;
            }
            visited.add(n);
            deque.addAll(n.neighbors);
            Node cloneN = map.getOrDefault(n,new Node(n.val)) ;
            List<Node> neighbor = new ArrayList<>();
            for (int i = 0; i < n.neighbors.size(); i++) {
                Node no = map.getOrDefault(n.neighbors.get(i),new Node(n.neighbors.get(i).val));
                neighbor.add(no);
                map.put(n.neighbors.get(i),no);
            }
            cloneN.neighbors = neighbor;
            map.put(n,cloneN);
        }
        return map.get(node);
    }
}
